洛谷 P1192 台阶问题

洛谷 P1192 台阶问题

链接

https://www.luogu.org/problem/P1092

题目

题目描述

有N级的台阶，你一开始在底部，每次可以向上迈最多K级台阶（最少1级），问到达第N级台阶有多少种不同方式。

输入格式

两个正整数N，K。

输出格式

一个正整数，为不同方式数，由于答案可能很大，你需要输出ans mod 100003后的结果。

输入输出样例

输入 #1

5 2

输出 #1

8

说明/提示

对于20%的数据,有N≤10,K≤3;

对于40%的数据，有N≤1000;

对于100%的数据，有N≤100000,K*≤100。

思路

算法以前是见过的，但是学名我忘了emmmm，不知道算不算动态规划。

假设要到第3个台阶，最大可以走三阶，我们可以0-1-2-3，也可以0-1-3,0-2-3,0-3，一共有四种方法，第一步到的就是123其中之一：

1. 如果到1，再到3的方法和0-2的方法一样（2种），之后再走一步
2. 到2，再到3和0-1的方法一样（1种）
3. 直接到3，和0-0一样（1种）

就可以得到

f[i] += f[i-j]

这个式子，之后放到代码中组合，最后得到的f[n]就是我们需要的答案。

代码

#include<iostream>
 
using namespace std;

int main()
{
	int n, k;
	int f[100001] = { 0 };
	cin>>n>>k;
	f[0]=1;
	for(int i=1;i<=n;i++) 
	{
		for(int j=1;j<=k;j++) 
		{
			if(i>=j)
			{
				f[i] += f[i-j];
				f[i] = f[i]%100003;
			}
		}
	}
	cout<<f[n];
    return 0;
}